public class Cube
{
     static class BusyException
          extends Exception
     {
          public BusyException() { super("Busy"); }
     }

     static class Packet
     {
          private int mDestination;
          private byte[] mData;
          private int[] mRoute= new int[0];

          public Packet(int destination, byte[] data)
          {
               mDestination= destination;
               mData= data;
          }

          public int getDestination() { return mDestination; }
          public byte[] getData() { return mData; }

          public void routedBy(Node node) 
          {
               int[] copy= mRoute;
               mRoute= new int[mRoute.length+1];
               System.arraycopy(copy, 0, mRoute, 0, copy.length);
               mRoute[mRoute.length-1]= node.getNumber();
          }

          public String toString() 
          {
               String str= getData().length +" bytes => node " +
                    getDestination() + ", route= ";

               for (int n= 0; n< mRoute.length; n++) 
                    str += mRoute[n] +" ";

               return str;
          }
     }

     static class Node
          extends Thread
     {
          private int mNumber;
          private boolean mBusy= false;
          private Node[] mNeighbours= new Node[0];
          private Packet mPacket;

          public Node(int number) { mNumber= number; }

          public int getNumber() { return mNumber; }

          public void addNeigbour(Node neighbour)
          {
               Node[] copy= mNeighbours;
               mNeighbours= new Node[mNeighbours.length+1];
               System.arraycopy(copy, 0, mNeighbours, 0, copy.length);
               mNeighbours[mNeighbours.length-1]= neighbour;
          }

          // Thread processing loop sleeps until there is something to do.
          // While busy will not accept any more packets.
          public void run() 
          {
               while (true) {
                    try {
                         synchronized (this) {
                              mBusy= false;
                              wait();
                              mBusy= true;
                         }
                         work();
                         mPacket= null;
                    }
                    catch (InterruptedException e) {
                         break;
                    }
               }
          }

          public synchronized boolean isBusy() { return mBusy; }

          private void work()
          {
               if (mPacket.getDestination() == getNumber()) {
                    System.err.println("Got packet: " +mPacket);
                    return;
               }

               // Random sleep so this node may be busy when asked to work 
               // on another packet - which will force a different route
               try { sleep(((long)(Math.random()*10)+4)*100); }
               catch (InterruptedException e) { }

               int[] route= getRoute();
               int n= 0;
               while (true) {
                    try {
                         getNeighbour(route[n]).submit(mPacket);
                         break;
                    }
                    catch (BusyException e) {
                         n= n == route.length -1 ? 0 : ++n;
                    }
               }
          }

          // Give this node a packet to work on. May be for this node or
          // may need sending on to another node closer to the packets
          // destination node. If the node is busy, tell the user to back
          // off by throwing an exception
          private void submit(Packet packet) 
               throws BusyException
          {
               if (isBusy()) 
                    throw new BusyException();

               mPacket= packet;
               mPacket.routedBy(this);
               synchronized (this) {
                    notify();
               }
          }

          // Calcultes possibilities for the next step on the shortest route
          // to the packets destination node
          private int[] getRoute()
          {
               int[] route= new int[0];
               int xor= getNumber() ^ mPacket.getDestination();
               int mask= xor;
               int bits= 0;
               for (;mask > 0; mask >>= 1, bits++);
               for (int shift= 0; shift < bits; shift++) {
                    int test= 1 << shift;
                    if ((xor | test) == xor) {
                         int num= getNumber() ^ test;
                         int[] copy= route;
                         route= new int[route.length+1];
                         System.arraycopy(copy, 0, route, 0, copy.length);
                         route[route.length-1]= num;
                    }
               }
               return route;
          }

          private Node getNeighbour(int number)
          {
               for (int n= 0; n< mNeighbours.length; n++) {
                    if (mNeighbours[n].getNumber() == number) 
                         return mNeighbours[n];
               }
               return null;
          }

          public String toString()
          {
               String str= getNumber() +" => ";
               for (int n= 0; n< mNeighbours.length; n++) 
                    str += mNeighbours[n].getNumber() +" ";
               return str;
          }
     }

     static class Hypercube
     {
          private Node[] mNodes;

          public Hypercube(int dimensions)
          {
               mNodes= new Node[(int) Math.pow(2, dimensions)];

               // Create the nodes
               for (int n= 0; n< mNodes.length; n++) 
                    mNodes[n]= new Node(n);

               // Set appropriate neighbours and start each node
               for (int n= 0; n< mNodes.length; n++) {
                    for (int d= 0, mask= 1; d< dimensions; d++, mask <<= 1) 
                         mNodes[n].addNeigbour(mNodes[mNodes[n].getNumber() ^ mask]);
                    mNodes[n].start();
               }
          }

          public int getSize() { return mNodes.length; }

          public void submit(int node, Packet packet) 
               throws BusyException
          {
               mNodes[node].submit(packet);
          }
     }

     public static void main(String[] argv)
          throws Exception
     {
          int dimensions= argv.length < 1 ? 3 : Integer.parseInt(argv[0]);

          Hypercube cube= new Hypercube(dimensions);
          Thread.sleep(1*100);

          // Keep on banging pakcets into the 1st node with a destination of the
          // the furthest away node. Routes will be different as the nodes take
          // a random time to forward packets.
          while (true) {
               for (int d= 0; d< dimensions; d++) {
                    while (true) {
                         try {
                              cube.submit(0, 
                                   new Packet(cube.getSize()-1, "Fenway Park".getBytes()));
                              break;
                         }
                         catch (BusyException e) {
                              Thread.sleep(10);
                         }
                    }
               }
          }
     }
}